package com.xiaoyg.algorithm.sort;

import java.util.Arrays;

public class InsertionSort {

    public static void main(String[] args) {
        int[] values = {17,14,13,29,25,8,4};
        System.out.println("values数组原始顺序："+ Arrays.toString(values));
        values = sortArray(values);
        System.out.println("values数组排序后顺序："+ Arrays.toString(values));
    }

    public static int [] sortArray(int[] nums){
        int preIndex = 0;
        int currentValue = 0;
        for (int i = 0; i < nums.length - 1; i++){
            //已排序的数组最后一个下标
            preIndex = i;
            //无序的第一个数字
            currentValue = nums[i + 1];
            //当前无序的数字与有序的数组比较，从向右移动，给当前值留个位置
            while (preIndex >= 0 && currentValue < nums[preIndex]){
                nums[preIndex + 1] = nums[preIndex];
                preIndex -- ;
            }
            //当前值插入有序数组的位置
            nums[preIndex + 1] = currentValue;
        }
        return nums;
    }
}
